/**
 * @author ghp
 * @date 2023/6/17
 * @title
 * @description
 */
class Solution {

    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int r, int c) {
        if (r > board.length - 1 || r < 0 || c > board[0].length - 1 || c < 0 // 越界，结束递归
                || board[r][c] == '.' // 当前节点已遍历，结束递归
                || board[r][c] != word.charAt(index)) { // 当前路径已经出现一个不符合的单词了，结束递归
            return false;
        }
        if (index == word.length() - 1) {
            // index的长度等于word（因为从0开始计数，所以word长度要-1），说明已经再board中找到了word
            return true;
        } else {
            char temp = board[r][c];
            board[r][c] = '.';
            boolean f = dfs(board, word, index + 1, r + 1, c) || dfs(board, word, index + 1, r - 1, c)
                    || dfs(board, word, index + 1, r, c + 1) || dfs(board, word, index + 1, r, c - 1);
            board[r][c] = temp;
            return f;
        }
    }

}